#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<stack>
//和文件读入及输入数据处理相关的库
#include <fstream>
#include <iomanip>
#include <sstream>
using namespace std;

typedef struct arcNode
{
	int ToNode_ID;//用来表示指向的结点对应的编号，同时他也是头结点所对应的下标
	string relationship;//用来表示顶点和边之间的关系
	struct arcNode* nextarc;//用来指向下一个结点的指针域
}ArcNode;//边结构体

typedef string Info_Name;
typedef string Node_Type;
typedef struct vNode
{
	Info_Name name;//表示结点的名称
	Node_Type type;//表示结点的类型
	int color;//表示结点在可视化的情况下需要分配的颜色
	ArcNode* firstarc;//结点指向的第一个结点。
}VNode;//顶点结构体

typedef struct 
{
	VNode* vNodeList;//结点表
	int nodeNumb;//表示邻接表所带有的结点的个数
	int edgeNumb;//表示邻接表所存在的边的个数
}adjGraph;//邻接表

typedef struct 
{
	int ID;//入队的结点所对应的id编号
	int parent;//当前入队的顶点的路径直接前驱在该队列所在的下标
	string relationship;//前一个结点和当前结点的关系
}Queue;//特殊队列结点

typedef struct
{
	int recommendID;//推荐的电影的编号
	int pathNumb;//两结点间存在的路径的数量
}RecommendNode;//推荐顺序表结点

//全局变量区
extern adjGraph movieG;//电影图谱
extern map<string, int> nodeIndexTable;//结点编号索引表

//函数区
void Initial_Index_TableAndGrahp_Nodes();//初始化哈希索引表以及图的初始结点
void CreateGraph();//读取relationship文件，然后建图
void OutputGraphy();//输出图，用于测试图是否建好
void menuFunction();//菜单函数
void printMenuHead();//打印菜单头的函数
void EasySearchBaseOnPerson(string search_information);//根据提供的演员或者导演来查找他们的作品
void intelligentQandA(string node, string relationship);//智能问答
void SearchRaletionship(string object1, string object2);//关系查找
void bfsFindPath(string u, string v);//bfs查找并输出最短路径及其关系
void movieRecommend(string basedMovie);//电影推荐模块

//效果不佳的方案：
//void DFS_back(string u, string v, vector<int> node_path, int node_index, vector<string> relationship_path);
//深度搜索获取两个结点间的全部路径。